package com.navy.search;

/**
 * 二分查找法
 */
public class BinarySearch {

    /**
     * 二分查找模板
     *
     * @param array
     * @param value
     * @return
     */
    public static int binarySearchTemplate(int[] array, int value) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >>> 1;
            int midValue = array[mid];
            if (value < midValue) { //
                end = mid - 1;
            } else if (midValue < value){
                start = mid + 1;
            } else {
                // todo 带补充的语句, 以下三选一
                // return mid;
                // end = mid - 1;
                // start = mid + 1;
            }
        }
        return start;
    }

    /**
     * 返回第一个大于等于Value的值
     *
     * @param array
     * @param value
     * @return
     */
    public static int binarySearchLowerBound(int[] array, int value) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >>> 1;
            int midValue = array[mid];
            if (value < midValue) {
                end = mid - 1;
            } else if (midValue < value) {
                start = mid + 1;
            } else { // ==
                end = mid - 1;
            }
        }
        return start;
    }

    /**
     * 返回第一个大于Value的值
     *
     * @param array
     * @param value
     * @return
     */
    public static int binarySearchUpperBound(int[] array, int value) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >>> 1;
            int midValue = array[mid];
            if (value < midValue) {
                end = mid - 1;
            } else if (midValue < value) {
                start = mid + 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    /**
     * 标准二分查找法, 在一个数据找找寻value。
     *
     * @param array 数组 升序排序
     * @param value 要找的数
     * @return 如果数组存在与value值相等的元素时，返回首次对半找到的值的index；否则返回-1
     */
    public static int binarySearch(int[] array, int value) {
        int start = 0, end = array.length - 1;  // [start, end] 区间，start和end都能取得
        while (start <= end) {
            int mid = (start + end) >>> 1;
            if (array[mid] < value) {
                start = mid + 1;
            } else if (value < array[mid]) {
                end = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 标准二分查找法, 在一个数据找找寻value。
     *
     * @param array 数组 升序排序
     * @param value 要找的数
     * @return 如果数组存在与value值相等的元素时，返回首次对半找到的值的index；否则返回-1
     */
    public static int binarySearchEndOpen(int[] array, int value) {
        int start = 0, end = array.length;  // [start, end) 比区间，end不能去到, end指向非查找目标
        while (start < end) {
            int mid = (start + end) >>> 1;
            if (array[mid] < value) {
                start = mid + 1;
            } else if (value < array[mid]) {
                end = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 二分查找
     *
     * @param array
     * @param value
     * @return >= value的最左侧值
     */
    public static int binarySearchLeftMost(int[] array, int value) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >>> 1;
            int midValue = array[mid];
            if (value <= midValue) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    /**
     * 二分查找
     *
     * @param array
     * @param value
     * @return <= value的最右侧值
     */
    public static int binarySearchRightMost(int[] array, int value) {
        int start = 0, end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >>> 1;
            int midValue = array[mid];
            if (value < midValue) {
                end = mid -1;
            } else {
                start = mid + 1;
            }
        }
        return start - 1;
    }

    /**
     * 二分查找
     *
     * @param array
     * @param value
     * @return > value的最左侧值 (第一个元素)
     */
    public static int binarySearchLeft(int[] array, int value) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >>> 1;
            int midValue = array[mid];
            if (value < midValue) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    /**
     * 二分查找
     *
     * @param array
     * @param value
     * @return < value 第一个值
     */
    public static int binarySearchRight(int[] array, int value) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >>> 1;
            int midValue = array[mid];
            if (value <= midValue) {
                end = mid -1;
            } else {
                start = mid + 1;
            }
        }
        return start - 1;
    }
}
